|
The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test. Its original version, due to Gary L. Miller, is deterministic, but the determinism relies on the unproven Extended Riemann hypothesis; Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm. ==Concepts== Just like the Fermat and Solovay–Strassen tests, the Miller–Rabin test relies on an equality or set of equalities that hold true for prime values, then checks whether or not they hold for a number that we want to test for primality. First, a lemma about square roots of unity in the finite field Z/''p''Z, where ''p'' is prime and ''p'' > 2. Certainly 1 and −1 always yield 1 when squared modulo ''p''; call these trivial square roots of 1. There are no ''nontrivial'' square roots of 1 modulo ''p'' (a special case of the result that, in a field, a polynomial has no more zeroes than its degree). To show this, suppose that ''x'' is a square root of 1 modulo ''p''. Then: : : In other words, prime ''p'' divides the product By Euclid's lemma it divides one of the factors or implying that ''x'' is congruent to either 1 or −1 modulo ''p''. Now, let ''n'' be prime with ''n'' > 2. It follows that is even and we can write it as 2''s''·''d'', where ''s'' and ''d'' are positive integers (''d'' is odd). For each ''a'' in (Z/''n''Z) *, either : or : for some 0 ≤ r ≤ ''s'' − 1. To show that one of these must be true, recall Fermat's little theorem, that for a prime number n: : By the lemma above, if we keep taking square roots of ''a''''n''−1, we will get either 1 or −1. If we get −1 then the second equality holds and it is done. If we never get −1, then when we have taken out every power of 2, we are left with the first equality. The Miller–Rabin primality test is based on the contrapositive of the above claim. That is, if we can find an ''a'' such that : and : for all 0 ≤ r ≤ ''s'' − 1, then ''n'' is not prime. We call ''a'' a witness for the compositeness of ''n'' (sometimes misleadingly called a ''strong witness'', although it is a certain proof of this fact). Otherwise ''a'' is called a ''strong liar'', and ''n'' is a strong probable prime to base ''a''. The term "strong liar" refers to the case where ''n'' is composite but nevertheless the equations hold as they would for a prime. Every odd composite ''n'' has many witnesses ''a'', however, no simple way of generating such an ''a'' is known. The solution is to make the test probabilistic: we choose a non-zero ''a'' in Z/''n''Z randomly, and check whether or not it is a witness for the compositeness of ''n''. If ''n'' is composite, most of the choices for ''a'' will be witnesses, and the test will detect ''n'' as composite with high probability. There is, nevertheless, a small chance that we are unlucky and hit an ''a'' which is a strong liar for ''n''. We may reduce the probability of such error by repeating the test for several independently chosen ''a''. For testing large numbers, it is common to choose random bases ''a'', as, a priori, we don't know the distribution of witnesses and liars among the numbers 1, 2, ..., ''n'' − 1. In particular, Arnault gave a 397-digit composite number for which all bases ''a'' less than 307 are strong liars. As expected this number was reported to be prime by the Maple isprime() function, which implemented the Miller–Rabin test by checking the specific bases 2,3,5,7, and 11. However, selection of a few specific small bases can guarantee identification of composites for ''n'' less than some maximum determined by said bases. This maximum is generally quite large compared to the bases. As random bases lack such determinism for small ''n'', specific bases are better in some circumstances.抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Miller–Rabin primality test」の詳細全文を読む スポンサード リンク
|